

import java.util.Iterator;
import java.util.Random;


public class RandomQueue<Item> implements Iterable<Item>  {
	
	private Item[] a = (Item[]) new Object[4];
	private int N = 0;
	
	//Constructor
	public RandomQueue(){
		
	}
	
	//Methods
	private void resize(int max){
		Item[] temp = (Item[]) new Object[max];
			for (int i=0;i<N;i++)
			{
				if (i<a.length)
					temp[i]=a[i];					
			}
			a = temp;
	}
	
	
	public Boolean isEmpty(){
		if (this.a.length==0)
			return true;
		return false;
	}
	
	public int size(){
		return N;
	}
	
	public void enqueue(Item item){
		if (a.length==N){
			resize(2*a.length);
		}		
		this.a[N++]=item;
		
	}
	
	public Item dequeue(){
		if (N>0){
		if (a.length==N/4){
			resize(a.length/2);			
		}
		int R= (int) (Math.random()*N);
		Item drawnItem = a[R];
		a[R] = a[N-1];
		N--;
		return drawnItem;}
		return a[N];
	}
	
	public Item sample(){
		if (N>0){
			int R= (int) (Math.random()*N);
			Item drawnItem = a[R];
			return drawnItem;}
			return a[N];
	}
	
	public String toString(){
		String s="";
		for (int i=0;i<N;i++){
			s+=a[i];
		}
		return s;
	}

	@Override
	public Iterator<Item> iterator() {
		return (Iterator<Item>) new randomArrayIterator();
	}
	
	private class randomArrayIterator implements Iterator<Item>{
		Item[] IterateThis = a.clone();
		int IN = N;
		public boolean hasNext(){
			if(IN==0)
				return false;
			return true;			
		}
		public Item next(){
			int R= (int) (Math.random()*IN);
			Item drawnItem = IterateThis[R];
			IterateThis[R] = IterateThis[IN-1];
			IN--;
			return drawnItem;}
		public void remove(){}
	}
	
}

